混合易失和非易失主存的日志结构文件系统NOVA[FAST'16]随笔二

序言

没成想，本想用一篇博文写完的，偶然发现博文后面文字显示不了，最后才发现是因为符号原因“＜＞”隐藏了后面的文字表示。那么为了把故事讲完整，所以我写了这篇后续博客。内容完全接着NOVA随笔一继续把故事都唠叨完吧。直接入正题啦！

NOVA实现

NVMM数据结构和空间管理

索引节点表（inode table）

NOVA初始分配每个索引结点表为2MB块组的索引结点，每个索引结点以128字节边界对齐，所以给定一个索引结点号能够很容易定位到目标索引节点。NOVA以round-robin顺序来分配新的索引结点到每个索引节点表中，这样索引结点能够比较平均地分布到众多索引节点表(inode tables)。为了减少索引节点表尺寸，每个NOVA inode包含一个有效位（valid bit）并且NOVA重新使用无效的索引结点用于新的文件或目录。每个CPU一个inode table可避免索引节点的分配争用并允许在故障恢复中并行扫描（parallel scanning）。每个inode包含日志的头尾指针，日志以4KB页的链表存在，并且日志尾指针总是指向最新的提交的日志项（log entry）。

Journal

一个NOVA的journal是一个4KB大小的循环缓存（circular buffer),并且NOVA用一个(enqueue,dequeue)指针对来管理每个journal。对于创建操作，NOVA journal目录的日志尾指针和新的索引节点有效位。NOVA允许每个核一次打开一个事务并且每个CPU允许并发事务执行。每次目录操作，内核虚拟文件系统层锁住所有受影响的inodes，保证并发事务不会操作同一个索引节点。

NVMM空间管理

为了使得NVMM分配和回收快速，NOVA将NVMM划分成pools,每个CPU一个，并且在DRAM中保持NVMM空闲页列表。如果在当前的CPU pool中没有可用的页时，NOVA将从最新的pool中分配页并且使用pool锁来提供保护。为了减少分配尺寸，NOVA采用红黑树（red-black tree）以便保持空闲列表按地址排序，允许高效合并以及提供O(log n）回收。

原子性和写顺序性
NOVA提供元数据、数据和mmap更新的原子性，通过使用结合日志结构和journaling两种方法的技术实现。该技术使用如下三种机制:

• 64位原子更新：当前处理器支持易失性内存的64位原子写。NOVA使用64位原地写以便直接修改元数据，如文件的读访问时间等某些操作，并且使用64位原子写通过更新索引节点的日志尾指针来提交更新到日志中。
• Logging：NOVA采用索引结点日志以便记录修改单个索引结点的所有操作。这些操作包括write，msync和chmod。每个索引结点的日志是相互独立存在的。
• 轻量级Journaling：对于目录操作要求改变多个索引结点的操作如create，unlink和rename，NOVA采用轻量级的日志提供原子性。任何时间内，任何journal的数据是小的，不会超过64字节。

写顺序

NOVA依赖三个写顺序规则确保一致性。首先，它在更新日志尾指针前提交数据和日志条目到NVMM中；第二，它在传输更新前提交journal的数据到NVMM；最后，在回收过时版本之前提交数据页的新版本。如果NOVA运行在一个支持clflushopt,clwb和PCOMMIT指令的系统上，将使用如下面的伪代码确保写顺序性。

new_tail = append_to_log(inode->tail, entry);
// writes back the log entry cachelines
clwb(inode->tail, entry->length);
sfence(); // orders subsequent PCOMMIT
PCOMMIT(); // commits entry to NVMM
sfence(); // orders subsequent store
inode->tail = new_tail;
1
2
3
4
5
6
7

如果平台不支持上述新指令，NOVA采用movntq非时序移动指令绕过CPU高速缓存层以便直接写NVMM，并且结合clflush和sfence确保写顺序性。

目录操作
NOVA对目录操作进行了优化，包括link，symlink以及rename。它将目录分成两个部分：一个是存在NVMM中的目录索引结点日志，一个是存在DRAM中的radix tree。图3表明了这些部件的关系。目录日志（directory log）包括了两个条目：目录条目（directory entries，简称dentry）和索引结点更新条目（inode update entries）。Dentries包括子文件/目录的名字，它的索引结点号（inode number）以及时间戳（timestamp）。为了加速目录条目的检索，NOVA将每个目录索引结点保存在DRAM中的radix tree中。NOVA使用当前CPU的Journal去原子地更新目录日志的尾指针并且设置新的索引结点的有效位。

原子的mmap
DAX(Direct Access）文件系统允许应用程序通过load和store指令去直接访问NVMM，通过将物理的NVMM文件数据页映射到应用程序物理地址空间中。DAX-mmap绕过文件系统页高速缓存（page cache）并且避免了paging开销，程序员现有可用的原子性机制包括64位写、fences以及高速缓存刷新指令（clflusｈ），仅用这些原语构建强健的非易失数据结构是非常困难的。为了解决这个问题，NOVA提出了atomic-mmap，它是一个具有强一致性的直接NVMM访问模型。由于NOVA对于文件数据使用写时拷贝技术并且立即回收过时的数据页（stale data pages），它不支持DAX-mmap。Atomic-mmap比DAX-mmap有更高的开销但是提供更强的一致性保证。

垃圾回收
NOVA的日志采用链表（linked list）形式并且仅包含元数据，是的垃圾回收简单高效。NOVA垃圾回收机制分Fast GC和Thorough GC。分别如下介绍。

Fast GC
Fast GC不要求任何的拷贝（copying）。如果在一个日志页中的所有条目过时（dead），那么Fast GC通过从日志链表中删除该页来回收日志空间。如图5（a）展示一个快速日志垃圾回收的例子。

Thorough GC
在Fast GC日志扫描期间，NOVA记录每个日志空间存活日志（log）条目所占的空间比例。如果存活的条目所占的空间少于日志空间的50%，NOVA就利用Fast GC结束后的Thorough GC来拷贝获得条目到一个新的更加紧实的日志版本中，更新DRAM数据结构指向新的日志，然后使用新的日志原子地替换旧的日志，最后并回收该旧日志。具体例子图5（b）所示。

关机和恢复
当NOVA重新挂载文件系统时，它将重构需要的DRAM数据结构。由于应用程序可能仅访问文件系统的一部分索引节点（inodes），所以NOVA采用一个称为延迟重建（lazy rebuild）的策略以便减少恢复时间。它推迟重建radix树和索引结点，直到文件系统第一次访问该索引结点时才重建。这个策略加速了恢复过程并且减少了DRAM的消耗。

正常关机的恢复
对于正常关机操作，NOVA将NVMM页分配状态保存到恢复索引结点日志（recovery inode’s log）中并且在接下来的remount操作中恢复该分配状态。这个过程中，NOVA不需要扫描任何的索引节点日志，所以恢复过程很快。

失败恢复
在系统故障发生是，NOVA通过扫描索引结点日志来重建NVMM分配器信息。NOVA的日志扫描过程是快速的，原因有两点，其一是每个CPU的索引结点表和每个索引结点均有一个log允许日志恢复的巨大的并行性；第二点是因为NOVA的日志仅包含元数据而不包含数据页，日志很短。NOVA的失败恢复过程包括两步：

1. NOVA检查每个journal并且回滚任何未提交的事务以便恢复文件系统到一致性状态。
2. NOVA在每个CPU中运行一个恢复进程并且并行扫描索引节点表，为索引节点表中的每一个有效的索引节点执行日志扫描。

NVMM保护
为了保护文件系统并且防止NVMM免受流浪写的持久腐蚀影响，NOVA必须确保只有系统软件才能够访问NVMM。NOVA采用PMFS相同的保护机制。在文件系统挂载时，整个NVMM区域被映射为只读。当NOVA需要写NVMM页时，它通过禁止（disable）处理器的写保护控制（CR0.WP）以便打开一个写窗口（write window）。当CR0.WP被清理时，内核软件以ring 0权限运行则可以写内核空间中标记为只读的页。写完后，NOVA又重置CR0.WP以便关闭该写窗口。

评价

NOVA采用了因特尔持久内存模拟平台（Intel PM Emulation Platform，简称PMEP）。

• 用PMEP模拟了不同的NVM特征；
• 模拟了clwb/PCOMMIT的延迟。

具体情况见表1所示：

NOVA提供了低延迟的原子性，如下图所示：

NOVA采用了Filebench工作负载包括fileserver、webproxy、webserver和varmail去评估NOVA的应用程序级性能。Filebench工作负载特征见表2所示。

NOVA获得了高性能并且有强数据一致性保证。

垃圾回收效率
NOVA的性能随着运行时间的增加保持稳定，原因是在长期的运行过程中，Fast GC回收了主要的过时页（stale pages）。如下图所示：

恢复开销
NOVA使用DRAM去维持NVMM空闲页列表（free page lists），所以在文件系统挂载时必须重建。NOVA通过延迟地重建索引节点信息，保持短的日志并且执行并行的日志扫描来加速恢复过程。为了测量恢复开销，采用了表4中的三种工作负载。每种工作负载代表了文件系统的一种不同的使用情况：Videoserver包含少量的大尺寸请求的大文件访问，mailserver包含了大量的小文件并且请求大小比较小，而Filesever介于两者之间。详情见表4

表5总结了结果。正常关机，NOVA在1.2ms时间恢复文件系统，原因是NOVA不需要扫描索引结点日志。在系统故障后，NOVA的恢复时间随着索引结点的数量的增大而增长，文件越多，文件日志越多并且随着IO操作的进行文件越来越碎片化以致文件日志变得越来越长。基于STT-RAM上比基于PCM的恢复快是因为NOVA需要读日志以便重构NVMM空闲页列表，而PCM有比STT-RAM更高的读延迟。在PCM和STT-RAM中，NOVA能够在116ms时间内恢复50GB数据，恢复带宽超过400GB/s。

总结

加州大学Jian Xu和Steven Swanson等人发表在2016年文件和存储技术（File and storage technology）国际顶级A类会议上的NOVA，它是一个基于混合易失/非易失主内存的日志结构文件系统。NOVA扩展LFS思想以便管理NVMM，它的多日志（multi-log）设计使得有快速的和有效的垃圾回收并且在系统故障后快速恢复。NOVA提供更强的一致性和原子性保证的同时优于现有的文件系统。

详细请参阅原文

NOVA: A Log-structured File System for Hybrid Volatile/Non-volatile Main Memories[FAST’16]，Jian Xu and Steven Swanson
NOVA: A Log-structured File System for Hybrid Volatile/Non-volatile Main Memories[slides]